package cc.willrock.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BucketSort {
	/*
	 * 最好O(n)) 平均O(n) 最坏O(n)
	 */
	public static int[] sort(int [] a){
		//build bucket
		List<List<Integer>> list = new ArrayList<List<Integer>>();	
		for(int i = 0;i<bucketNum(a.length);i++){
			ArrayList<Integer> l = new ArrayList<Integer>();
			list.add(l);
		}
		
		//put into bucket
		for(int i  = 0;i<a.length;i++){
			int p=hash(a[i]);
			List<Integer> ll= list.get(p);
			ll.add(a[i]);
		}
		
		//exact from bucket
		int idx = 0;
		for(int i=0;i<list.size();i++){
			List<Integer> ll= list.get(i);
			Collections.sort(ll);
			while(ll.size()>0){
				a[idx]=ll.get(0);
				ll.remove(0);
				idx++;
			}
		}
		
		return a;
	}
	
	public static int bucketNum(int n){
		return n;
	}
	public static int hash(int n){
		return n/3;
	}
	public static void main(String[] args){
		int a[] = {7,5,13,2,14,1,6};
		System.out.println(sort(a));
	}
}
